#include "../tools.h"

// 至少有一半是有序的
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.size() == 0) return -1;
        if(nums.size() == 1) return nums[0] == target ? 0 : -1;

        int left = 0, right = nums.size() - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            cout << left << "-" << right << "-" << mid << endl;
            // ! 一侧只有一个元素，无法判断是否有序，直接处理
            if(target == nums[mid]) return mid;
            if(target < nums[mid]){
                if(left == mid) left = mid + 1;
                // 左侧有序
                else if(nums[left] < nums[mid]){
                    if(nums[left] <= target) right = mid - 1;
                    else left = mid + 1;
                }
                // 右侧有序
                else{
                    right = mid - 1;
                }
            }
            else if(nums[mid] < target){
                // ! 一侧只有一个元素，无法判断是否有序，直接处理
                if(right == mid) right = mid - 1;
                // 右侧有序
                else if(nums[mid] < nums[right]){
                    if(target <= nums[right]) left = mid + 1;
                    else right = mid - 1;
                }
                // 左侧有序
                else{
                    left = mid + 1;
                }
            }
            
        }
        return -1;
    }
};


int main(int argc, char const *argv[])
{
    Solution s;

    vector<int> nums = {3, 1};
    int target = 1;

    int res = s.search(nums, target);
    cout << res << endl;

    return 0;
}
